package com.algorithm.dynamic;

/**
 * @author xxy 动态规划，经典题目，背包问题
 * @create 2021 3 25 11:52
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        int[] w={1,4,3};//物品的重量
        int[] val={1500,3000,2000};//物品的价值
        int m=4;//背包的容量
        int n=val.length;//物品的个数
        int[][] v=new int[n+1][m+1];//v[i][j]表示在前i个物品中能够转入容量为背包中的最大价值
        int[][] path=new int[n+1][m+1];//为了记录放入商品的情况
        //背包问题
        for(int i=1;i<v.length;i++){
            for(int j=1;j<v[0].length;j++){
                if(w[i-1]>j){
                    v[i][j]=v[i-1][j];
                }else {
                    //v[i][j]=Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]);
                    if(v[i-1][j]<val[i-1]+v[i-1][j-w[i-1]]){
                        v[i][j]=val[i-1]+v[i-1][j-w[i-1]];
                        path[i][j]=1;
                    }else {
                        v[i][j]=v[i-1][j];
                    }
                }
            }
        }
        for (int i = 0; i < v.length; i++) {
            for (int j = 0; j < v[i].length; j++) {
                System.out.print(v[i][j]+" ");
            }
            System.out.println();
        }
        int i=path.length-1;
        int j=path[0].length-1;
        while (i>0&&j>0){
            if(path[i][j]==1){
                System.out.println(i+"放入背包");
                j-=w[i-1];
            }
            i--;
        }

    }
}
